package com.leetcode.根据数据结构分类.并查集;

/**
 * @author: ZhouBert
 * @date: 2021/3/18
 * @description: 695. 岛屿的最大面积
 * https://leetcode-cn.com/problems/max-area-of-island/
 */
public class B_695_岛屿的最大面积 {

	static B_695_岛屿的最大面积 action = new B_695_岛屿的最大面积();

	public static void main(String[] args) {
//		test1();
//		test2();
		test3();
	}

	public static void test1() {
		//4
		int[][] grid = {{1, 1, 0, 0, 0}, {1, 1, 0, 0, 0}, {0, 0, 0, 1, 1}, {0, 0, 0, 1, 1}};
		int res = action.maxAreaOfIsland(grid);
		System.out.println("res = " + res);
	}

	public static void test2() {
		//0
		int[][] grid = {{0, 0, 0, 0, 0, 0, 0, 0}};
		int res = action.maxAreaOfIsland(grid);
		System.out.println("res = " + res);
	}

	public static void test3() {
		//0
		int[][] grid = {{0, 1}, {1, 1}};
		int res = action.maxAreaOfIsland(grid);
		System.out.println("res = " + res);
	}


	/**
	 * 使用并查集
	 * 1.将同个岛屿进行合并；（由于遍历是往右往下的，那么寻找合并的方向是就是往左往上的）
	 * 2.遍历 parents ，使用 max 变量记录最大面积
	 * 其中需要考虑的细节：
	 * 1.合并的是 1 的位置，当 num(1) >= max 是才有意义
	 *
	 * @param grid
	 * @return
	 */
	public int maxAreaOfIsland(int[][] grid) {
		int m = grid.length;
		int n = grid[0].length;
		int size = m * n;
		InnerUnionFind unionFind = new InnerUnionFind(size);
		//遍历第一行(排除 0,0 )：往左合并
		int index = 1;
		//BUG 修复：当都是水时，此时 union find 出来的结果会是 1，只有岛屿存在时，推断才成立！
		boolean hasOneNum = grid[0][0] == 1;
		for (int i = 1; i < n; i++) {
			if (grid[0][i] == 1) {
				hasOneNum = true;
				if (grid[0][i - 1] == 1) {
					unionFind.union(index, index - 1);
				}
			}
			index++;
		}
		//从第二行开始，此时 往左并往上 遍历
		for (int i = 1; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (grid[i][j] == 1 ){
					hasOneNum = true;
					//往上合并
					if (grid[i - 1][j] == 1){
						unionFind.union(index, index - n);
					}

					//往左合并
					if (j != 0) {
						if (grid[i][j - 1] == 1) {
							unionFind.union(index, index - 1);
						}
					}
				}
				index++;
			}
		}
		if (!hasOneNum) {
			//如果都木有1
			return 0;
		}
		//最后遍历 parents
		//再次开一个数组进行记录（完成 hashMap 的功能）
		int[] recorder = new int[size];
		int max = 0;
		for (int i = 0; i < size; i++) {
			//BUG 修复：需要每个数字都进行归根处理才能保证最后每个元素指向都是根元素
			unionFind.find(i);
			int rIndex = unionFind.parents[i];
			recorder[rIndex]++;
			max = Math.max(max, recorder[rIndex]);
		}
		return max;
	}


	static class InnerUnionFind {
		int[] parents;
		int[] ranks;

		/**
		 * init union find
		 *
		 * @param capacity
		 */
		public InnerUnionFind(int capacity) {
			parents = new int[capacity];
			ranks = new int[capacity];
			for (int i = 0; i < capacity; i++) {
				parents[i] = i;
				ranks[i] = 1;
			}
		}

		public int find(int index) {
			if (parents[index] != index) {
				parents[index] = find(parents[index]);
			}
			return parents[index];
		}

		public void union(int index1, int index2) {
			int p1 = find(index1);
			int p2 = find(index2);
			if (p1 == p2) {
				return;
			}
			if (ranks[p1] == ranks[p2]) {
				ranks[p1]++;
				parents[p1] = p2;
			} else if (ranks[p1] < ranks[p2]) {
				parents[p1] = p2;
			} else {
				parents[p2] = p1;
			}
		}

		public boolean isSame(int index1, int index2) {
			return find(index1) == find(index2);
		}
	}
}
